﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeTop.复习九月份
{
    public class Solution516
    {
        int max = 0;
        public int LongestPalindromeSubseq1(string s)//递归全遍历超时
        {

            IList<char> path = new List<char>();
            DFS(s, 0, path);


            return max;

        }

        private void DFS(string s, int start, IList<char> path)
        {
            if (MyTest(path.ToArray()))
            {

                max = Math.Max(max, path.Count);

            }


            for (int i = start; i < s.Length; i++)
            {
                path.Add(s[i]);
                DFS(s, i + 1, path);
                path.RemoveAt(path.Count - 1);

            }
        }

        private bool MyTest(char[] chars)
        {

            int left = 0, right = chars.Length - 1;

            while (left < right)
            {
                if (chars[left] == chars[right])
                {


                    left++;
                    right--;

                }
                else
                {
                    return false;
                }

            }
            return true;
        }

        public int LongestPalindromeSubseq(string s)//递归全遍历超时
        {
            int curmax = 0;
            int len=s.Length;
            if (len == 1)
            {
                return 1;
            }
            int[][] dp= new int[len][];
            for (int i = 0; i < len; i++)
            {
                dp[i]= new int[len];
                dp[i][i]= 1;
            }
            for(int l = 2;l <= len; l++)
            {
                for(int i = 0;i <= len-l;i++)
                {
                    int j = i + l - 1;

                    if (s[j] == s[i])
                    {
                        if (l == 2)
                        {
                            dp[i][j] =  2;
                        }
                        else
                        {
                            dp[i][j] = dp[i + 1][j - 1] + 2;
                        }

                        
                    }
                    else
                    {
                        dp[i][j] = Math.Max(dp[i ][j - 1], dp[i + 1][j]); 
                    }

                    Console.WriteLine(dp[i][j]);
                    curmax = Math.Max(curmax, dp[i][j]);

                }

            }
            return curmax;

        }
    }
    class Program516
    {



        static void Main516(string[] args)
        {
            string s = "bbbab";


            Solution516 sol = new Solution516();
            int res = sol.LongestPalindromeSubseq(s);
            Console.WriteLine(res);
        }


    }








}
